Everything about Variable-length Code totally explained
In
coding theory a
variable-length code is a
code which maps source symbols to a
variable number of bits.
Variable-length codes can allow sources to be
compressed and decompressed with
zero error (
lossless data compression) and still be read back symbol by symbol. With the right coding strategy an
i.i.d. source may be compressed almost arbitrarily close to its
entropy. This is in contrast to fixed length coding methods, for which data compression is only possible for large blocks of data, and any compression beyond the logarithm of the total number of possibilities comes with a finite (though perhaps arbitrarily small) probability of failure.
Some examples of well-known variable-length coding strategies are
Huffman coding,
Lempel-Ziv coding and
arithmetic coding.
Extension of a code
The
extension of a code is the mapping of finite length source sequences to finite length bit strings, that's obtained by concatenating for each symbol of the source sequence the corresponding codeword produced by the original code.
Classes of variable-length codes
Variable-length codes can be strictly nested in order of decreasing generality as non-singular, uniquely decodable and instantaneous (prefix free). Instantaneous codes are always uniquely decodable, which in turn are always non-singular :
Non-singular codes
A code is
non-singular if each source symbol is mapped to a different non-empty bit string, for example the mapping from source symbols to bit strings is one-to-one.
